<!doctype html public "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<meta name="robot" content="index,follow">
<title>Module bnt - Generic binary tree - Forth Foundation Library</title>
</head>
<body>
<h2>bnt - Generic binary tree</h2>
<h3>Module Description</h3>
<p>The bnt module implements a generic unbalanced binary tree with the key
cell based. The implementation is non-recursive. Pay special attention to
the bnt-insert word. This word inserts new nodes in the tree. The input
parameters are the tree itself, the key, the node creation word and any
optional parameters for the node creation word. The bnt-insert word will
only call the node creation word if the key is unique in the tree. If so
the creation word is called and the resulting node is stored in the tree
and returned as output parameter with the true flag. If the key is not
unique the node creation word is not called and the current node with the
key is returned with the false flag and the optional parameters. In that
case the calling word can update this node with the optional parameters.
The stack notation of the node creation word is: i*x x bnn1 -- bnn2.
i*x are the optional parameters, x is the key, bnn1 is the parent node
and bnn2 is the returned tree node. See also [bnn] and [bcn] for examples
of node creation words.
</p>
<h3>Module Words</h3>
<dl>
</dl>
<h4>Generic binary tree structure</h4>
<dl>
<dt><a name="word1"><b>bnt%</b>	( -- n )</dt>
<dd>Get the required space for a bnt variable</dd>
</dl>
<h4>Tree creation, initialisation and destruction</h4>
<dl>
<dt><a name="word2"><b>bnt-init</b>	( bnt -- )</dt>
<dd>Initialise the tree</dd>
<dt><a name="word3"><b>bnt-(free)</b>	( xt bnt -- )</dt>
<dd>Free the nodes from the heap using xt</dd>
<dt><a name="word4"><b>bnt-create</b>	( "&lt;spaces&gt;name" -- ; -- bnt )</dt>
<dd>Create a named binary tree in the dictionary</dd>
<dt><a name="word5"><b>bnt-new</b>	( -- bnt )</dt>
<dd>Create a new binary tree on the heap</dd>
<dt><a name="word6"><b>bnt-free</b>	( bnt -- )</dt>
<dd>Free the tree node from the heap</dd>
</dl>
<h4>Member words</h4>
<dl>
<dt><a name="word7"><b>bnt-length@</b>	( bnt -- u )</dt>
<dd>Get the number of elements in the tree</dd>
<dt><a name="word8"><b>bnt-empty?</b>	( bnt -- flag )</dt>
<dd>Check for an empty tree</dd>
<dt><a name="word9"><b>bnt-compare@</b>	( bnt -- xt )</dt>
<dd>Get the compare execution token for comparing keys</dd>
<dt><a name="word10"><b>bnt-compare!</b>	( xt bnt -- )</dt>
<dd>Set the compare execution token for comparing keys</dd>
</dl>
<h4>Tree words</h4>
<dl>
<dt><a name="word11"><b>bnt-clear</b>	( xt bnt -- )</dt>
<dd>Delete all nodes in the tree using word xt</dd>
<dt><a name="word12"><b>bnt-insert</b>	( i*x xt x bct -- bnn1 true | i*x bnn2 false )</dt>
<dd>Insert a new unique node in the tree with key x, creation word xt and optional parameters</dd>
<dt><a name="word13"><b>bnt-delete</b>	( x bnt -- false | bnn true )</dt>
<dd>Delete key x from the tree, return the deleted node</dd>
<dt><a name="word14"><b>bnt-get</b>	( x bnt -- false | bnn true )</dt>
<dd>Get the node related to key x from the tree</dd>
<dt><a name="word15"><b>bnt-has?</b>	( x1 bnt -- flag )</dt>
<dd>Check if the key x1 is present in the tree</dd>
<dt><a name="word16"><b>bnt-execute</b>	( i*x xt bnt -- j*x )</dt>
<dd>Execute xt for every node in the tree</dd>
<dt><a name="word17"><b>bnt-execute?</b>	( i*x xt bnt -- j*x flag )</dt>
<dd>Execute xt for every node in the tree until xt returns true</dd>
</dl>
<h4>Inspection</h4>
<dl>
<dt><a name="word18"><b>bnt-dump</b>	( bnt -- )</dt>
<dd>Dump the tree node structure</dd>
</dl>
<h3>Examples</h3>
<pre>
include ffl/bnt.fs
include ffl/bni.fs
include ffl/str.fs


\ Example: store mountain positions in a binary tree


\ Create the generic binary tree in the dictionary

bnt-create mountains


\ Setup the compare word for comparing the mountain names

: mount-compare  ( str str - n = Compare the two mountain names )
  str^ccompare
;

' mount-compare mountains bnt-compare!


\ Extend the generic binary tree node with mountain positions fields

begin-structure mount%
  bnn%
  +field   mount&gt;node        \ Mountain structure extends the bnn structure
  ffield:  mount&gt;lng         \ Longitude position
  ffield:  mount&gt;lat         \ Latitude position
end-structure


\ Create the allocation word for the extended structure

: mount-new    ( F: r1 r2 -- ; x bnn1 -- bnn2 = Create a new mountain position variable with position r1 r2, name c-addr u and parent bnn1 )
  mount% allocate throw             \ Allocate the mountain variable
  &gt;r
  r@ mount&gt;node bnn-init            \ Initialise the binary tree node
  r@ mount&gt;lng f!                   \ Save the longitude position
  r@ mount&gt;lat f!                   \ Save the latitude position
  r&gt;
;

 
  
\ Add the mountain positions to the binary tree; the key is the mountain name in a (unique) dynamic string

27.98E0 86.92E0  ' mount-new  str-new dup s" mount everest" rot str-set  mountains bnt-insert [IF]
  .( Mountain:) bnn-key@ str-get type .(  added to the tree.) cr
[ELSE]
  .( Mountain was not unique in tree) cr drop fdrop fdrop 
[THEN]

45.92E0  6.92E0  ' mount-new  str-new dup s" mont blanc" rot str-set   mountains bnt-insert [IF]
  .( Mountain:) bnn-key@ str-get type .(  added to the tree.) cr
[ELSE]
  .( Mountain was not unique in tree) cr drop fdrop fdrop
[THEN]

43.35E0 42.43E0 ' mount-new   str-new dup s" mount elbrus" rot str-set  mountains bnt-insert [IF]
  .( Mountain:) bnn-key@ str-get type .(  added to the tree.) cr
[ELSE]
  .( Mountain was not unique in tree) cr drop fdrop fdrop
[THEN]


\ Find a mountain in the binary tree

str-new value mount-name

s" mont blanc" mount-name str-set

mount-name mountains bnt-get [IF]
  .( Mount:)      dup bnn-key@ str-get type 
  .(  latitude:)  dup mount&gt;lat f@ f. 
  .(  longitude:)     mount&gt;lng f@ f. cr
[ELSE]
  .( Mount:) mount-name str-get type .(  not in tree.) cr
[THEN]


s" vaalserberg" mount-name str-set

mount-name mountains bnt-get [IF]
  .( Mount:)      dup bnn-key@ str-get type 
  .(  latitude:)  dup mount&gt;lat f@ f. 
  .(  longitude:)     mount&gt;lng f@ f. cr
[ELSE]
  .( Mount:) mount-name str-get type .(  not in tree.) cr
[THEN] 


\ Word for printing the mountain positions

: mount-emit ( mount -- = Print mountain )
  dup bnn-key@ str-get type ."  --&gt; "
  dup mount&gt;lat f@ f. ." - "
      mount&gt;lng f@ f. cr
;


\ Print all mountain positions

' mount-emit mountains bnt-execute       \ Execute the word mount-emit for all entries in the tree


\ Example mountains iterator

\ Create the tree iterator in the dictionary

mountains bni-create mount-iter          \ Create an iterator named mount-iter on the mountains tree

\ Moving the iterator

mount-iter bni-first nil&lt;&gt;? [IF]
  .( First mount:) dup bnn-key@ str-get type 
  .(  latitude:)   dup mount&gt;lat f@ f. 
  .(  longitude:)      mount&gt;lng f@ f. cr
[ELSE]
  .( No first mountain.) cr
[THEN]

mount-iter bni-last nil&lt;&gt;? [IF]
  .( Last mount:) dup bnn-key@ str-get type 
  .(  latitude:)  dup mount&gt;lat f@ f. 
  .(  longitude:)     mount&gt;lng f@ f. cr
[ELSE]
  .( No last mountain.) cr
[THEN]


\ Word for freeing the tree node 

: mount-free     ( mount -- = Free the node in the tree )
  dup bnn-key@ str-free
  
  free throw
;

\ Cleanup the tree

' mount-free mountains bnt-clear
</pre>
<hr>
<div align="center">generated 24-Jul-2010 by <b>ofcfrth-0.10.0</b></div>
</body>
</html>
